1. Field of the Invention
The present invention relates generally to a scheduling apparatus and a scheduling method for fetching information elements out of a plurality of ques for storing inputted information elements and more particularly to a scheduling apparatus and a scheduling method that are used for, e.g., routers.
2. Related Background Art
There exists a data structure, known as a queue, for transferring and receiving data between two processes each having a different speed. The queue is defined as a data structure consisting of a plurality of data elements. The data elements thereof are fetched based on constraints of FIFO (First In First Out). The queues have been used in a variety of apparatuses, and one of techniques making use of the plurality of queues is called a fair queuing method.
Herein, with reference to FIGS. 13, 14, the fair queuing method will be discussed by exemplifying a router for connecting two subnets A, B to each other as illustrated in FIG. 12.
As shown in FIG. 13, a router 50 using the fair queuing method includes a packet classifying unit 51, a plurality of queues 52, an output buffer 53 and a scheduling unit 55. Each queue 52 is provided corresponding to a transmitting station (terminal) connected to the subnet A, and the packet classifying unit 41 supplies packets transmitted from a given transmitting terminal, to the queue corresponding to this transmitting terminal.
The scheduling unit 55 goes on cyclically specifying the respective queues 52 and, if the queue 52 designated as a processing target is stored with a packet, fetches the packet from this queue 32 and further supplies an output buffer 53 with the packet. That is, the scheduling unit 55, as schematically shown in FIG. 14, cyclically designates the queues 52.sub.1 -52.sub.3 as processing targets and, if the packets exist in the queue 52 designated as the processing target, fetches one packet out of this queue.
Thus, according to the fair queuing method, an opportunity for fetching the data elements (packets) is cyclically given to the plurality of queues.
Known also is a router that performs the above-described queue control in consideration of a packet size. In this type of router, the processing target queues are cyclically changed, and there is judged whether each queue designated as the processing target is stored with the packets. Then, if stored with the packets, the size data corresponding to that queue is incremented by one bit, and the packet is fetched out of such a queue that the size data is coincident with the packet size.
According to the router involving use of the fair queuing method described above, the opportunity for transmitting the packets can be given more impartially to the respective transmitting terminals than by the prior art router (for transferring the packets based on the FIFO system) for determining a packet transmitting sequence without considering the transmitting terminals.
In the router using the fair queuing method, however, if no packets exist in a certain queue (transmitting terminal) when the packet transmitting opportunity is given to this queue, this fact does not reflect in processes for the packet transmitting opportunities after the next time onward. Therefore, in the case of observing it at a long time interval, it follows that partial processing is executed for each of the transmitting terminals. Further, the packet fetching from the relevant queue is executed alternately with the packet fetching from other queue (or confirmation of status of other queue). Hence, even if a certain transmitting terminal generates the packets burstwise, the packets transmitted by the router in response thereto are spoiled in terms of their burstwise properties.